package _03_recursion;

import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/6/2 - 13:10
 * 杨辉三角（动态规划优化，带一维数组缓存）个人感觉性能比较好，而且更优雅
 * <p>
 * ①
 * ① ①
 * ① ② ①
 * ① ③ ③ ①
 * ① ④ ⑥ ④ ①
 */
public class PascalTriangleTest3_cache {

    // 控制台打印杨辉三角(带缓存)
    @Test
    public void test() {
        print(10);
    }

    /**
     * 使用一维数组做缓存
     *
     * @param cache
     * @param i 当前打印的行
     */
    void createRow(int[] cache, int i) {
        if (i == 0) {
            cache[i] = 1;
            return;
        }
        for (int j = i; j > 0; j--) {
            // 当前[i][j]的值 = [i-1][j] + [i-1][j-1]
            cache[j] = cache[j] + cache[j - 1];
        }
    }

    /**
     * 打印杨辉三角(带缓存)
     *
     * @param row 高度
     */
    void print(int row) {
        // 缓存数组
        int[] cache = new int[row];
        for (int i = 0; i < row; i++) {
            createRow(cache, i);
            // 打印前置的空格
            for (int k = 0; k < row - i - 1; k++) {
                System.out.print("\t");
            }
            for (int j = 0; j < i + 1; j++) {
                System.out.print(cache[j] + "\t\t");
            }
            System.out.println();
        }
    }
}
